package demo1;

import java.util.HashMap;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    //岛屿的最大面积
    int maxArea = 0, curArea = 0;
    public int maxAreaOfIsland(int[][] grid) {
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[i].length; j++){
                if(grid[i][j] == 1) {
                    curArea = 0;
                    dfs(i, j, grid);
                    maxArea = Math.max(maxArea, curArea);
                }
            }
        }
        return maxArea;
    }

    private void dfs(int x, int y, int[][] grid) {
        if(x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || grid[x][y] == 0) return;
        if(grid[x][y] == 1) {
            curArea ++;
            grid[x][y] = 0;
        }
        dfs(x - 1, y, grid);
        dfs(x + 1, y, grid);
        dfs(x, y - 1, grid);
        dfs(x, y + 1, grid);
    }

    //完全平方数
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        for (int i = 0; i <= n; i++) dp[i] = i;
        for (int i = 2, j = i*i; j <= n; i++, j = i*i) {
            for (int k = j; k <= n; k++) {
                dp[k] = Math.min(dp[k-j] + 1, dp[k]);
            }
        }
        return dp[n];
    }

    //网咯延迟时间
    int count = 0;
    public int networkDelayTime(int[][] times, int n, int k) {
        int index = -1;
        for (int i = 0; i < times.length; i++) {
            if(times[i][0]==k) {
                index = i;
                break;
            }
        }
        child(times,index);
        return count;
    }

    private void child(int[][] times, int index){

    }
}


















